// https://leetcode.cn/problems/largest-rectangle-in-histogram/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 单调栈解决柱状图中最大矩形面积问题
// 2. 维护高度递增的单调栈（存储下标）
// 3. 遇到较小高度时，计算以栈顶高度为高的最大矩形
// 4. 末尾添加高度0确保所有柱子都被处理
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <stack>

class Solution 
{
public:
    int largestRectangleArea(vector<int>& heights) 
    {
        int m = heights.size();

        heights.push_back(0);
        stack<int> st;
        st.push(-1);

        int maxArea = 0;
        for (int i = 0 ; i <= m ; i++)
        {
            while (st.top() != -1 && heights[st.top()] > heights[i])
            {
                int height = heights[st.top()];
                st.pop();
                int width = i - st.top() - 1;
                maxArea = max(maxArea, width * height);
            }
            st.push(i);
        }

        return maxArea;
    }
};

int main()
{
    vector<int> height1 = {2,1,5,6,2,3}, height2 = {2,4};
    Solution sol;

    cout << sol.largestRectangleArea(height1) << endl;
    cout << sol.largestRectangleArea(height2) << endl;

    return 0;
}